package Projet;

import java.util.*;
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author DESGROUAS Romain L3INFO
 */

public class UnionFind {

	private int[] parent;
	private int[] rang;
	private int[] rep;	
	/***************************************************************************
									CONSTRUCTEUR
						 INITIALISE LA STRUCTURE CLASSE-UNION	
	***************************************************************************/
	public UnionFind(int max)
	{
		parent = new int[max];
		rang = new int[max];
		rep = new int[max];
		for(int i=0;i<max;i++){
			rep[i]=i;
		}
		
	}
	/**************************************************************************/
	
	/***************************************************************************
									FIND
				RETOURNE LA CLASSE DE L'ENTIER PASSE EN PARAMETRE	
	***************************************************************************/
	public int Find(int i)
	{
		int p = parent[i];
		if (p==0)
		{
			return i;
		}
		return Find(p);
	}
	/**************************************************************************/
	
	/***************************************************************************
									UNIONPARRANG
	REUNI LES CLASSES DES ENTIERS PASSES EN PARAMETRE EN FONCTION DE LEURS RANGS	
	***************************************************************************/
	public int UnionParRang(int i, int j)
	{
		int racine1 = Find(i);
		int racine2 = Find(j);
		if (racine2 == racine1)
		{
			return 0;
		}
		if (rang[racine1] >= rang[racine2])
		{
			parent[racine2] = racine1;
			if(rang[racine1] == rang[racine2])
			{
				rang[racine1]++;
			}
			return i;
		}
		else
		{
			parent[racine1] = racine2;
			return j;
		}
	}
	/**************************************************************************/
	
	/***************************************************************************
									FINDCOMP
				IDENTIQUE A FIND MAIS AVEC COMPRESSION DES CHEMINS	
	***************************************************************************/
	public int FindComp(int i)
	{
		int p = parent[i];
		if (p == 0)
		{
			return i;
		}
		return parent[i] = Find(p);
	}
	/**************************************************************************/
	
	/***************************************************************************
								 UNIONPARRANGCOMP
			IDENTIQUE A UNIONPARRANG MAIS AVEC COMPRESSION DES CHEMINS	
	***************************************************************************/
	public void UnionParRangComp(int i, int j)
	{
		int racine1 = FindComp(i);
		int racine2 = FindComp(j);
		if (racine2 == racine1)
		{
			return;
		}
		if (rang[racine1] >= rang[racine2])
		{
			parent[racine2] = racine1;
			if(rang[racine1] == rang[racine2])
			{
				rang[racine1]++;
			}
		}
		else
		{
			parent[racine1] = racine2;
		}
	}
	/**************************************************************************/

	/***************************************************************************
									TOSTRING
						  AFFICHE L'ETAT DE LA STRUCTURE	
	***************************************************************************/
	public String toString()
	{
		System.out.print("         ");
		for(int i=1;i<parent.length;i++)
		{
			System.out.print(i+"  ");
		}
		String chaine="\nparents [";
		for(int i=1;i<parent.length;i++)
		{
			if(parent[i]==0){
				chaine=chaine+"-";
			}
			else{
				chaine=chaine+parent[i];
			}
			
			if(i!=parent.length-1)
			{
				chaine=chaine+", ";
			}
		}
		chaine=chaine+"]\nrangs   [";
		for(int i=1;i<rang.length;i++)
		{
			chaine=chaine+rang[i];
			if(i!=parent.length-1)
			{
				chaine=chaine+", ";
			}
		}
		chaine=chaine+"]\n";		
		return chaine;
//		return "  parents " + Arrays.toString(parent) + "\n  rangs   " 
//				+ Arrays.toString(rang) + "\n";
	}
	/**************************************************************************/
}
